/* falloc.c - The file space management routines for dbm. */

/*  GNU DBM  - DataBase Manager (database subroutines) by Philip A. Nelson
    Copyright (C) 1989  Free Software Foundation, Inc.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    You may contact the author by:
       e-mail:  phil@wwu.edu
      us-mail:  Philip A. Nelson
                Computer Science Department
                Western Washington University
                Bellingham, WA 98226
        phone:  (206) 676-3035

*************************************************************************/

#include "gdbm.h"
#include "extern.h"
#include "gdbmutils.h"

#include <stdlib.h>
#include <stdio.h>

static int free_adr;		/* When allocating a block, we may need */
static int free_size;		/* to "free" part of a previous block. */

static int _file_alloc(dbm_file_info *, int, int);
static void get_avail_block(dbm_file_info *, int, avail_block *, int *);
static void write_avail_block(dbm_file_info *, avail_block *, int *);
static void adjust_header(dbm_file_info *, int, int, int, int, int, int, int);

/* Allocate space in the file DBF for a block NUM_BYTES in length.  Return
   the file address of the start of the block.  Allocation is done on a
   first fit basis.  The avail structure is changed by this routine if a
   change is needed.  If AT_BLOCK_START is true, the allocation is wanted
   at the start of read/write block.  This is used for allocating new buckets,
   new directories or any other structure that should start at the start
   of a block.  If an error occurs, the value of 0 will be returned.  */

int _dbm_alloc(dbm_file_info * dbf, int num_bytes, int at_block_start)
{
	int new_address;

	/* Get the new address. */
	new_address = _file_alloc(dbf, num_bytes, at_block_start);

	/* Free unused space on previous block if there is any. */
	if (free_size != 0)
		_dbm_free(dbf, free_adr, free_size);

	return new_address;
}


/* This is the routine that does all the work for _dbm_alloc except doing the
   final freeing of space freed by a block allocation.  This is to allow
   _dbm_free to work correctly and stop recursion. */

static int _file_alloc(dbm_file_info * dbf, int num_bytes, int at_block_start)
{
	int file_adr;		/* The address of the block. */
	int temp;		/* For temporary storage.  */
	avail_elem *av_el;	/* For temporary accesss to elements. */

	/*
	 * Start by checking the avail structure.  Load the avail block that
	 * has the "best" chance of having the correct element in it.
	 */
	temp = num_bytes >> AVAIL_BITS;
	if (temp >= AVAIL_SIZE)
		temp = AVAIL_SIZE - 1;
	temp = dbf->header.avail_list[temp];
	get_avail_block(dbf, temp, dbf->avail, &dbf->avail_adr);

	/* Initialize free_size so we don't free something already freed. */
	free_size = 0;

	/* Now look in the avail list. */
	while (dbf->avail_adr != 0)
	{
		/* Check the local block for what we want. */
		for (temp = 0; temp < dbf->avail->count; temp++)
		{
			av_el = &dbf->avail->av_table[temp];
			if (av_el->av_size >= num_bytes
			    && (!at_block_start || (av_el->av_adr
					    % dbf->header.block_size) == 0))
			{
				/* This is the block to allocate. */
				file_adr = av_el->av_adr;

				/*
				 * Delete the smaller item and remember it
				 * for later freeing.
				 */
				free_adr = av_el->av_adr + num_bytes;
				free_size = av_el->av_size - num_bytes;
				dbf->avail->count -= 1;
				for (; temp < dbf->avail->count; temp++)
				{
					dbf->avail->av_table[temp] = dbf->avail->av_table[temp + 1];
				}

				/* Write the updated current avail block. */
				_dbm_update(dbf, 0x77777701, file_adr, num_bytes,
					    free_size, dbf->avail_adr);
				write_avail_block(dbf, dbf->avail, &dbf->avail_adr);
				return file_adr;
			}
		}

		/* Nothing on this block.  How about the next. */
		get_avail_block(dbf, dbf->avail->next_block, dbf->avail, &dbf->avail_adr);
	}

	/*
	 * We did not allocate from the avail list, so allocate at the end of
	 * the file.
	 */
	if (at_block_start && (dbf->header.file_size % dbf->header.block_size) != 0)
	{
		/*
		 * Adjust file length to end of a block and set up for later
		 * freeing of the unused space in the previous block.
		 */
		temp = dbf->header.file_size / dbf->header.block_size + 1;
		file_adr = temp * dbf->header.block_size;
		free_adr = dbf->header.file_size;
		free_size = file_adr - dbf->header.file_size;
		dbf->header.file_size = file_adr + num_bytes;
	}
	else
	{
		/* Allocate at next byte. */
		file_adr = dbf->header.file_size;
		free_size = 0;
		dbf->header.file_size += num_bytes;
	}

	/* Update dbf->header on disk by calling _dbm_update. */
	_dbm_update(dbf, 0x77777702, file_adr, num_bytes, free_adr, free_size);

	/* Return the address. */
	return file_adr;

}

/* Free space of size NUM_BYTES in the file DBF at file address FILE_ADR.  Make
   it avaliable for reuse through _dbm_alloc.  This routine changes the
   avail structure.  The value TRUE is returned if there were errors.  If no
   errors occured, the value FALSE is returned. */

int _dbm_free(dbm_file_info * dbf, int file_adr, int num_bytes)
{
	int temp;
	int temp1;

	/* Put it into the avail structure in sorted order by size. */
	temp = num_bytes >> AVAIL_BITS;
	if (temp >= AVAIL_SIZE)
		temp = AVAIL_SIZE - 1;
	temp = dbf->header.avail_list[temp];
	get_avail_block(dbf, temp, dbf->avail, &dbf->avail_adr);

	/* Find the correct block. */
	while (dbf->avail->next_block != 0
	 && dbf->avail->av_table[dbf->avail->count - 1].av_size < num_bytes)
		get_avail_block(dbf, dbf->avail->next_block, dbf->avail, &dbf->avail_adr);

	/* Find the correct place in the block; */
	temp = 0;
	while (temp < dbf->avail->count && dbf->avail->av_table[temp].av_size <= num_bytes)
		temp++;

	/* Move all down. */
	for (temp1 = dbf->avail->count; temp1 > temp; temp1--)
		dbf->avail->av_table[temp1] = dbf->avail->av_table[temp1 - 1];

	/* Add it now. */
	dbf->avail->av_table[temp].av_adr = file_adr;
	dbf->avail->av_table[temp].av_size = num_bytes;
	dbf->avail->count += 1;
	_dbm_update(dbf, 0x77777703, file_adr, num_bytes,
		    dbf->avail_adr, dbf->avail->count);
	write_avail_block(dbf, dbf->avail, &dbf->avail_adr);

	/*
	 * Do we need more space?  We do if the current updated block is
	 * full.
	 */

	if (dbf->avail->count == dbf->avail->size)
	{
		avail_block *block;	/* The pointer to an avail block. */
		avail_block *new_block;	/* The pointer the a new avail block. */
		int curr_block;	/* The address of the current block. */
		int prev_block;	/* The address of the previous block. */
		int next_block;	/* The address of the next block. */
		int new_adr;	/* The address of the new block. */
		int count;	/* The number of items in the current avail
				 * block. */
		int temp_adr;	/* Used to force get_avail_block to read. */

		/* Allocate space for another avail block. */
		block = (avail_block *) malloc(dbf->header.block_size);

		count = dbf->avail->count;

		/* Can we share with previous block? */
		prev_block = dbf->avail->prev_block;
		if (prev_block != 0)
		{
			temp_adr = 0;
			get_avail_block(dbf, prev_block, block, &temp_adr);
			if (block->count < block->size / 2)
			{
				/* Adjust elements between the two blocks. */
				temp = count - ((count + block->count) / 2);	/* The number to copy. */
				for (temp1 = 0; temp1 < temp; temp1++)
					block->av_table[temp1 + block->count] = dbf->avail->av_table[temp1];
				for (temp1 = 0; temp1 < count - temp; temp1++)
					dbf->avail->av_table[temp1] = dbf->avail->av_table[temp1 + temp];
				block->count += temp;
				dbf->avail->count -= temp;

				/* Adjust the pointers in the header. */
				adjust_header(dbf, prev_block, block->av_table[0].av_size,
				  block->av_table[block->count - 1].av_size,
					      dbf->avail_adr, dbf->avail->av_table[0].av_size,
					      dbf->avail->av_table[dbf->avail->count - 1].av_size,
					      dbf->avail->next_block);

				/*
				 * Update the disk.  _dbm_update writes
				 * current header.
				 */
				_dbm_update(dbf, 0x77777704, dbf->avail_adr, count,
					    prev_block, block->count - temp);
				write_avail_block(dbf, block, &prev_block);
				write_avail_block(dbf, dbf->avail, &dbf->avail_adr);

				/* Return with no errors. */
				free(block);
				return FALSE;
			}
		}

		/* Can we share with next block? */
		next_block = dbf->avail->next_block;
		if (next_block != 0)
		{
			temp_adr = 0;
			get_avail_block(dbf, next_block, block, &temp_adr);
			if (block->count < block->size / 2)
			{
				/* Adjust elements between the two blocks. */
				temp = count - ((count + block->count) / 2);	/* The number to copy. */
				for (temp1 = block->count - 1; temp1 >= 0; temp1--)
					block->av_table[temp1 + temp] = block->av_table[temp1];
				for (temp1 = 0; temp1 < temp; temp1++)
					block->av_table[count - temp + temp1] = dbf->avail->av_table[temp1];
				block->count += temp;
				dbf->avail->count -= temp;

				/* Adjust the pointers in the header. */
				adjust_header(dbf, dbf->avail_adr, dbf->avail->av_table[0].av_size,
					      dbf->avail->av_table[dbf->avail->count - 1].av_size,
				     next_block, block->av_table[0].av_size,
				  block->av_table[block->count - 1].av_size,
					      block->next_block);

				/*
				 * Update the disk.  _dbm_update writes
				 * current header.
				 */
				_dbm_update(dbf, 0x77777705, dbf->avail_adr, count,
					    next_block, block->count - temp);
				write_avail_block(dbf, block, &next_block);
				write_avail_block(dbf, dbf->avail, &dbf->avail_adr);

				/* Return with no errors. */
				free(block);
				return FALSE;
			}
		}

		/* We can't share, so we must split the current block. */
		curr_block = dbf->avail_adr;
		new_block = (avail_block *) malloc(dbf->header.block_size);

		/* Use the allocation procedure that does not call _dbm_free. */
		new_adr = _file_alloc(dbf, dbf->header.block_size, TRUE);

		/*
		 * Make dbf->avail the previous current block.  It is
		 * possible _file_alloc changed the structure by a little by
		 * removing one item. It is guaranteed that _dbm_free was not
		 * called.
		 */
		get_avail_block(dbf, curr_block, dbf->avail, &dbf->avail_adr);
		count = dbf->avail->count;

		/* Do the split. */
		temp1 = count / 2;
		dbf->avail->next_block = new_adr;
		dbf->avail->count = temp1;
		new_block->size = dbf->avail->size;
		new_block->prev_block = dbf->avail_adr;
		new_block->next_block = next_block;
		new_block->count = count - temp1;
		for (temp = 0; temp1 + temp < count; temp++)
			new_block->av_table[temp] = dbf->avail->av_table[temp + temp1];

		/* Adjust the pointers in the header. */
		adjust_header(dbf, dbf->avail_adr, dbf->avail->av_table[0].av_size,
			   dbf->avail->av_table[temp1 - 1].av_size, new_adr,
			      new_block->av_table[0].av_size,
		new_block->av_table[count - temp1 - 1].av_size, next_block);


		_dbm_update(dbf, 0x77777706, dbf->avail_adr, count, new_adr, next_block);
		/*
		 * Update next block. It is already read in, so just update
		 * it.
		 */
		if (next_block != 0)
		{
			block->prev_block = new_adr;
			write_avail_block(dbf, block, &next_block);
		}
		write_avail_block(dbf, new_block, &new_adr);
		write_avail_block(dbf, dbf->avail, &dbf->avail_adr);

		/*
		 * Now that the split is complete, we can free any space left
		 * unused by the call to _file_alloc.
		 */
		if (free_size != 0)
			_dbm_free(dbf, free_adr, free_size);

		free(block);
		free(new_block);
	}

	/* No errors were found. */
	return FALSE;
}


/* Gets the avail block at AV_ADR in file DBF and put it into AVAIL_BLOCK.
   CUR_ADR is the address of the block in AVAIL_BLOCK so it is possible
   that this call does nothing but verify that AV_ADR is in AVAIL_BLOCK. */
static void get_avail_block(dbm_file_info * dbf, int av_adr,
			        avail_block * avail_block, int *cur_adr)
{
	int num_bytes;		/* For reading. */

	if (*cur_adr != av_adr)
	{
		*cur_adr = av_adr;
		if (*cur_adr != 0)
		{
			num_bytes = fseek(dbf->desc, *cur_adr, SEEK_SET);
			if (num_bytes != 0)
				_dbm_fatal(dbf, "lseek error");
			num_bytes = fread(avail_block, 1, dbf->header.block_size, dbf->desc);
			if (num_bytes != dbf->header.block_size)
				_dbm_fatal(dbf, "read error");
		}
	}
}


/* Writes the AVAIL_BLOCK to file DBF at address CUR_ADR. */
static void write_avail_block(dbm_file_info * dbf, avail_block * avail_block, int *cur_adr)
{
	int num_bytes;

	/* Update the disk. */
	num_bytes = fseek(dbf->desc, *cur_adr, SEEK_SET);
	if (num_bytes != 0)
		_dbm_fatal(dbf, "lseek error");
	num_bytes = fwrite(avail_block, 1, dbf->header.block_size, dbf->desc);
	if (num_bytes != dbf->header.block_size)
		_dbm_fatal(dbf, "write error");

	fflush(dbf->desc);
}


/* Adjust the avail pointers to point correctly. */
static void adjust_header(dbm_file_info * dbf, int block1, int low1, int high1,
			      int block2, int low2, int high2, int next)
{
	int temp;

	/* Truncate the bits into indices in avail_list. */
	low1 = (low1 >> AVAIL_BITS) + 1;
	high1 = high1 >> AVAIL_BITS;
	low2 = low2 >> AVAIL_BITS;
	high2 = high2 >> AVAIL_BITS;

	/* Update for the first block. */
	if (low1 >= AVAIL_SIZE)
		return;
	if (high1 >= AVAIL_SIZE)
		high1 = AVAIL_SIZE - 1;
	for (temp = low1; temp <= high1; temp++)
		if (dbf->header.avail_list[temp] == block2)
			dbf->header.avail_list[temp] = block1;

	/* Update for the second block. */
	if (low2 >= AVAIL_SIZE)
		return;
	if (high2 >= AVAIL_SIZE)
		high2 = AVAIL_SIZE - 1;
	if (low2 == high1)
		low2 += 1;
	if (next == 0)
		high2 = AVAIL_SIZE - 1;
	for (temp = low2; temp <= high2; temp++)
		if (dbf->header.avail_list[temp] == block1)
			dbf->header.avail_list[temp] = block2;

}



/* Repair the avail structure.  dbmopen found the file in a state where the
   last operation to write the header came from falloc.  UPDATE_CODE tells
   which update operation was last and PARAM1 through PARAM4 give the details. */

void _dbm_alloc_repair(dbm_file_info * dbf, int update_code, int param1,
		           int param2, int param3, int param4)
{
	int index;		/* A general index varaible. */

	switch (update_code)
	{
	case 1:		/* _file_alloc - updating current avail
				 * block. param1 = address of new allocation.
				 * param2 = size of new allocation. param3 =
				 * size of unused portion. param4 = address
				 * of avail block. */

		/* Get the block that was being updated. */
		get_avail_block(dbf, param4, dbf->avail, &dbf->avail_adr);

		/* Search for the allocated entry. */
		index = 0;
		while (index < dbf->avail->count
		       && dbf->avail->av_table[index].av_adr != param1)
			index++;

		/*
		 * If it is not found, then the write was successful and we
		 * must free it.
		 */
		if (index == dbf->avail->count)
			_dbm_free(dbf, param1, param2 + param3);
		break;


	case 2:		/* _file_alloc - allocating at the end of the
				 * file. param1 = address of new allocation.
				 * param2 = size of new allocation. param3 =
				 * address of unused portion of previous
				 * block. param4 = size of unused portion.  */

		/* The easiest solution is to free both blocks. */
		_dbm_free(dbf, param1, param2);
		_dbm_free(dbf, param3, param4);
		break;

	case 3:		/* _dbm_free - updating current avail block.
				 * param1 = address of new available block.
				 * param2 = size of new avaliable block.
				 * param3 = address of the avail block.
				 * param4 = size of avail block.  */

		/* Get the block that was being updated. */
		get_avail_block(dbf, param3, dbf->avail, &dbf->avail_adr);

		/* If the count is correct, the block was written. */
		if (param4 != dbf->avail->count)
			_dbm_free(dbf, param1, param2);
		break;

	case 4:		/* _dbm_free - splitting current avail block.
				 * Sharing with the previous block. param1 =
				 * address of current block. param2 = size of
				 * current block before split. param3 =
				 * address of previous block. param4 = size
				 * of previous block before split. */

		{
			avail_block *block1, *block2;	/* Blocks for making
							 * corrections. */
			int adr1, adr2;	/* Addresses of the blocks. */

			/* Allocate the space. */
			block1 = (avail_block *) malloc(dbf->header.block_size);
			block2 = (avail_block *) malloc(dbf->header.block_size);

			/* Get the block that was to be split. */
			adr1 = 0;
			get_avail_block(dbf, param1, block1, &adr1);

			/* Check to see which ones were changed. */
			if (block1->count == param2)
			{
				/* Current was not changed. */
				int temp, temp1;

				/* Get the block that was to receive items. */
				adr2 = 0;
				get_avail_block(dbf, param3, block2, &adr2);

				temp = param2 - ((param2 + param4) / 2);	/* The number to copy. */
				if (block2->count == param4)
				{
					/* Previous was not changed, fix it. */
					for (temp1 = 0; temp1 < temp; temp1++)
						block2->av_table[temp1 + param4] = block1->av_table[temp1];
					write_avail_block(dbf, block2, &adr2);
				}

				/* Fix up "current" block. */
				for (temp1 = 0; temp1 < param2 - temp; temp1++)
					block1->av_table[temp1] = block1->av_table[temp1 + temp];
				block1->count -= temp;
				write_avail_block(dbf, block1, &adr1);
			}

			free(block1);
			free(block2);

		}
		break;

	case 5:		/* _dbm_free - splitting current avail block.
				 * Sharing with the next block. param1 =
				 * address of current block. param2 = size of
				 * current block before split. param3 =
				 * address of next param4 = size of unused
				 * portion before split.  */
		{
			avail_block *block1, *block2;	/* Blocks for making
							 * corrections. */
			int adr1, adr2;	/* Addresses of the blocks. */

			/* Allocate the space. */
			block1 = (avail_block *) malloc(dbf->header.block_size);
			block2 = (avail_block *) malloc(dbf->header.block_size);

			/* Get the block that was to be split. */
			adr1 = 0;
			get_avail_block(dbf, param1, block1, &adr1);

			/* Check to see which ones were changed. */
			if (block1->count == param2)
			{
				/* Current was not changed. */
				int temp, temp1;

				/* Get the block that was to receive items. */
				adr2 = 0;
				get_avail_block(dbf, param3, block2, &adr2);

				temp = param2 - ((param2 + param4) / 2);	/* The number to copy. */
				if (block2->count == param4)
				{
					/* Next was not changed, fix it. */
					for (temp1 = param4 - 1; temp1 >= 0; temp1--)
						block2->av_table[temp1 + temp] = block2->av_table[temp1];
					for (temp1 = 0; temp1 < temp; temp1++)
						block2->av_table[temp1] = block1->av_table[param2 - temp + temp1];
					write_avail_block(dbf, block2, &adr2);
				}

				/* Fix up "current" block. */
				block1->count -= temp;
				write_avail_block(dbf, block1, &adr1);
			}

			free(block1);
			free(block2);

		}
		break;

	case 6:		/* _dbm_free - splitting current avail block.
				 * Creating a new block. param1 = address of
				 * current block. param2 = size of current
				 * block before the split. param3 = address
				 * of new block. param4 = address of the next
				 * block.
				 * 
				 * Note: This crash will loose a little free
				 * space. */
		{
			avail_block *block1, *block2;	/* Blocks for making
							 * corrections. */
			int adr1, adr2;	/* Addresses of the blocks. */

			/* Allocate the space. */
			block1 = (avail_block *) malloc(dbf->header.block_size);
			block2 = (avail_block *) malloc(dbf->header.block_size);

			/* Get the block that was to be split. */
			adr1 = 0;
			get_avail_block(dbf, param1, block1, &adr1);

			if (block1->count == param2)
			{
				/* The current block was not changed. */
				int temp, temp1;

				/*
				 * Resplit current.  Set the address for
				 * block2.
				 */
				adr2 = param3;

				/* Do the split. */
				temp1 = param2 / 2;
				block1->next_block = param3;
				block1->count = temp1;
				block2->size = block1->size;
				block2->prev_block = param1;
				block2->next_block = param4;
				block2->count = param2 - temp1;
				for (temp = 0; temp1 + temp < param2; temp++)
					block2->av_table[temp] = block1->av_table[temp + temp1];

				write_avail_block(dbf, block2, &adr2);
				write_avail_block(dbf, block1, &adr1);

				/* Make sure next_block is fixed. */
				if (param4 != 0)
				{
					adr2 = 0;
					get_avail_block(dbf, param4, block2, &adr2);
					block2->prev_block = param3;
					write_avail_block(dbf, block2, &adr2);
				}
			}

			free(block1);
			free(block2);

		}
		break;
	}
}


/* A debugging routine to see the stuff! */

void _dbm_print_avail_list(dbm_file_info * dbf)
{
	int temp;

	/* Start at the first block! */
	get_avail_block(dbf, dbf->header.avail_list[0], dbf->avail, &dbf->avail_adr);
	while (dbf->avail_adr != 0)
	{
		/* Print the block! */
		printf("\nblock = %d\nsize  = %d\ncount = %d\n", dbf->avail_adr,
		       dbf->avail->size, dbf->avail->count);
		for (temp = 0; temp < dbf->avail->count; temp++)
		{
			printf("  %15d   %10d \n", dbf->avail->av_table[temp].av_size,
			       dbf->avail->av_table[temp].av_adr);
		}

		/* How about the next. */
		get_avail_block(dbf, dbf->avail->next_block, dbf->avail, &dbf->avail_adr);
	}
}
